#include <iostream>
#include <vector>


int heapify(std::vector<int> & arr,int n ,int i){
    int largest = i;
    int left  = 2*i + 1;
    int right = 2*i + 2;
    // left
    if(left < n && arr[left] > arr[largest]){
        largest = left;
    }
    if(right < n && arr[right] > arr[largest]){
        largest = right;
    }
    
    if(largest != i){
        std::swap(arr[i],arr[largest]);
        heapify(arr,n,largest);
    }
    return 0;
}

int heap_sort(std::vector<int> & arr){
    int n = arr.size();
    for(int i = n/2-1 ;i>0;--i){
        heapify(arr,n,i);
    }
    for(int i = n-1;i>0;--i){
        std::swap(arr[0],arr[i]);
        heapify(arr,i,0);
    }
    return 0;
}

int main(){
    std::cout << "start" <<std::endl;
    std::vector<int> arr = {5,3,1,2,4};
    heap_sort(arr);
    for(int i =0;i<arr.size();i++){
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}